#include<iostream>
#include<stack>
using namespace std;

template<class K,class E>
struct AVLTreeNode {
    std::pair<K,E> pair;
    int bf;//平衡因子
    AVLTreeNode* leftChild;
    AVLTreeNode* rightChild;
    AVLTreeNode() {
        bf = 0;
        leftChild = rightChild = nullptr;
    }
    AVLTreeNode(std::pair<K, E>& p) {
        pair=p;
        bf = 0;
        leftChild = rightChild = nullptr;
    }
};

template<class K,class E>
class AVLTree {
private:
    AVLTreeNode<K,E>* root;
    int treeSize;
    void visit(AVLTreeNode<K,E>* node) {
        cout << "Key: " << node->pair.first 
             <<"Value: "<<node->pair.second
             <<"bf: " << node->bf << endl;
    }
    void inOrder(AVLTreeNode<K,E>* node);
    void dispose(AVLTreeNode<K,E>* node) {
        if (node != nullptr) {
            delete node;
        }
    }
public:
    AVLTree() {
        root = nullptr;
        treeSize = 0;
    };
    ~AVLTree();

    int getTreeSize() {
        return treeSize;
    }
    void insert(std::pair<K,E>&p);//插入值为v的节点
    void erase(K&k);//删除值为v的节点
    void ascendOutput() {
        inOrder(root);
    }
};

template<class K,class E>
AVLTree<K,E>::~AVLTree() {
    AVLTreeNode<K,E>* ptr = root;
    if (ptr != nullptr) {
        dispose(ptr->leftChild);
        dispose(ptr->rightChild);
        dispose(ptr);
    }
}

template<class K,class E>
void AVLTree<K,E>::inOrder(AVLTreeNode<K,E>* node) {
    if (node != nullptr) {
        inOrder(node->leftChild);
        visit(node);
        inOrder(node->rightChild);
    }
}

template<class K,class E>
void AVLTree<K,E>::insert(std::pair<K,E>&pair) {
    /*
    核心：寻找到距离插入位置最近的不平衡节点，在教材中称为节点A。经过比对，笔者认为教材思路最优。
    思路1：为每个节点都添加一个parent指针，指向父节点。之后从插入节点开始，不断向上更新父节点的bf值，
        直到找到A节点(https://blog.csdn.net/AngelDg/article/details/105797584)，即最近的bf=2的节点。
        这种思路的最终目的是寻找节点A并调整，教材思路为正向寻找，此思路为逆向寻找。
    思路2：教材思路。
        2.1从根节点开始搜索，确定插入位置，同时寻找最后的平衡因子为-1或1的节点，记为A。若找到相同关键字的元素，插入失败。
        2.2若没有这样的节点A，则插入后平衡。此时从根节点重新遍历一次，修改平衡因子，然后终止。
        2.3若bf(A)=1且新节点插入A的右子树，或bf(A)=-1且新节点插入A的左子树：A的新平衡因子是0。
            修改从A到新节点路径中节点的平衡因子，然后终止。
        2.4不平衡情况。这里不平衡节点即为节点A。
            2.4.1插入位置为不平衡点的左节点的左子树(ll)
            2.4.2插入位置为不平衡点的右节点的右子树(rr)
            2.4.3插入位置为不平衡点的左节点的右子树(lr)
            2.4.4插入位置为不平衡点的右节点的左子树(rl)
        确定不平衡类型，并执行相应的旋转。在从新子树根节点至新插入节点路径中，根据旋转需要修改相应的平衡因子

    注意，网络上有相当一部分方法是递归法，递归法在插入的过程中会导致每遇到一个节点就加入递归，如果AVL树高度较高，那么会严重
    浪费系统资源(每一次递归都是系统栈调用)，同时递归法思路并不是很清晰，笔者不建议使用递归法。
    另外，请注意，bf的计算不需要递归求节点高度才能计算，具体如何计算参照思路2。
    */
    //寻找到插入位置
    AVLTreeNode<K,E>* last = nullptr,
        * pp = nullptr,
        * p = root;//last即为A节点，pp是p的父节点
    while (p != nullptr) {
        pp = p;
        //确定节点A
        if (pp->bf == -1 || pp->bf == 1)
            last = pp;

        if (p->pair.first < pair.first)
            p = p->rightChild;
        else if (p->pair.first > pair.first)
            p = p->leftChild;
        else {
            //已存在此值
            p->pair.second = pair.second;
            return;
        }
    }

    if (pp == nullptr) {
        //root为空
        root = new AVLTreeNode<K,E>(pair);
        return;
    }

    if (pair.first < pp->pair.first)
    {
        pp->leftChild = new AVLTreeNode<K,E>(pair);
        p = pp->leftChild;
    }
    else
    {
        pp->rightChild = new AVLTreeNode<K,E>(pair);
        p = pp->rightChild;
    }

    treeSize++;
    //先判断A节点是否存在
    if (last == nullptr) {
        //A节点不存在，则插入前所有节点均为平衡状态
        //这时整棵树高度都发生了变化，需要从根开始调整bf
        AVLTreeNode<K,E>* cur = root;
        while (cur != p) {
            if (pair.first > cur->pair.first) {
                cur->bf--;
                cur = cur->rightChild;
            }
            else {
                cur->bf++;
                cur = cur->leftChild;
            }
        }
        return;
    }

    //A节点存在，且已经平衡
    if ((last->bf == -1 && pair.first < last->value) ||
        (last->bf == 1 && pair.second > last->value)) {
        AVLTreeNode<K,E>* cur = last;
        while (cur != p) {
            if (pair.first > cur->pair.first) {
                cur->bf--;
                cur = cur->rightChild;
            }
            else {
                cur->bf++;
                cur = cur->leftChild;
            }
        }
        return;
    }

    //程序运行到此，说明需要进行调整
    //即last->bf==-1&&v>last->value||last->bf==1&&v<last->value
    AVLTreeNode<K,E>* cur = last;
    while (cur != p) {
        if (pair.first > cur->pair.first) {
            cur->bf--;
            cur = cur->rightChild;
        }
        else {
            cur->bf++;
            cur = cur->leftChild;
        }
    }
    if (last->bf == 2) {
        AVLTreeNode<K,E>* lastLeft = last->leftChild;
        if (pair.first < lastLeft->value) {
            //ll
            AVLTreeNode<K,E>* n = last->leftChild;
            AVLTreeNode<K,E>* nRight = n->rightChild;
            AVLTreeNode<K,E>* nLeft = n->leftChild;
            AVLTreeNode<K,E>* lastRight = last->rightChild;

            last->rightChild = new AVLTreeNode<K,E>(pair);
            last->rightChild->rightChild = lastRight;
            last->rightChild->leftChild = nRight;
            last->value = n->value;
            last->leftChild = nLeft;
            last->bf = 0;
            last->rightChild->bf = 0;
            delete n;
        }
        else {
            //lr
            AVLTreeNode<K,E>* n = last->leftChild;
            AVLTreeNode<K,E>* nRight = n->rightChild;
            AVLTreeNode<K,E>* nRightLeft = nRight->leftChild;
            AVLTreeNode<K,E>* nRightRight = nRight->rightChild;
            AVLTreeNode<K,E>* lastRight = last->rightChild;

            last->rightChild = new AVLTreeNode<K,E>(pair);
            last->rightChild->rightChild = lastRight;
            last->rightChild->leftChild = nRightRight;
            nRight->rightChild = nullptr;
            n->rightChild = nRightLeft;
            nRight->leftChild = nullptr;
            last->pair = nRight->pair;

            //这里注意，lr的插入有两种情况：
            //1.插入节点在祖先节点的左子树
            //2.插入节点在祖先节点的右子树
            //这两种情况导致调整后，新根节点的左右子树bf有两种情况
            if (pair.first > last->pair.first) {
                last->leftChild->bf = 1;
                last->rightChild->bf = 0;
            }
            else {
                last->rightChild->bf = -1;
                last->leftChild->bf = 0;
            }
            last->bf = 0;

            delete nRight;
        }
    }
    else {
        AVLTreeNode<K,E>* lastRight = last->rightChild;
        if (pair.first < lastRight->pair.first) {
            //rl
            AVLTreeNode<K,E>* n = last->rightChild;
            AVLTreeNode<K,E>* nLeft = n->leftChild;
            AVLTreeNode<K,E>* nLeftRight = nLeft->rightChild;
            AVLTreeNode<K,E>* nLeftLeft = nLeft->leftChild;
            AVLTreeNode<K,E>* lastLeft = last->leftChild;

            last->leftChild = new AVLTreeNode<K,E>(pair);
            last->leftChild->leftChild = lastLeft;
            last->leftChild->rightChild = nLeftLeft;
            nLeft->leftChild = nullptr;
            n->leftChild = nLeftRight;
            nLeft->rightChild = nullptr;
            last->pair = nLeft->pair;

            //同lr，插入节点有两种插入请况
            if (pair.first > last->pair.first) {
                last->rightChild->bf = 1;
                last->leftChild->bf = 0;
            }
            else {
                last->leftChild->bf = -1;
                last->rightChild->bf = 0;
            }
            last->bf = 0;

            delete nLeft;
        }
        else {
            //rr
            AVLTreeNode<K,E>* n = last->rightChild;
            AVLTreeNode<K,E>* nLeft = n->leftChild;
            AVLTreeNode<K,E>* nRight = n->rightChild;
            AVLTreeNode<K,E>* lastLeft = last->leftChild;

            last->leftChild = new AVLTreeNode<K,E>(pair);
            last->leftChild->leftChild = lastLeft;
            last->leftChild->rightChild = nLeft;
            last->pair = n->pair;
            last->rightChild = nRight;
            last->bf = 0;
            last->leftChild->bf = 0;
            delete n;
        }
    }
}

template<class K,class E>
void AVLTree<K,E>::erase(K& k) {
    /*
    参考教材思路：
    1.寻找被删除节点父节点q，这里请注意，是实际被删除的节点；
    2.若|bf(q)|=1，则树无需平衡；
    3.若bf(q)=0，则向上回到父节点计算平衡因子，根据情况判断是否平衡；
    4.若|bf(q)|=2，则进行平衡(此时q其实就变为了插入节点的A节点)，其中：
        4.1.R0/L0不平衡无需向上继续判断；
        4.2.R1/L1,R-1/L-1不平衡需要向上继续判断。
    如何向上平衡？可以添加parent指针，也可以使用递归，这里笔者使用栈来实现此过程。
    若p为q的左子树:
        R0不平衡：bf(p)=0;
        R1不平衡，bf(p)=1;
        R-1不平衡，bf(p)=-1。
    L型不平衡同理。
    */
    AVLTreeNode<K,E>* pre=nullptr,*ptr = root;
    stack<AVLTreeNode<K,E>*>s;
    while (ptr!=nullptr&&ptr->pair.first!=k) {
        s.push(ptr);
        pre = ptr;
        if (k > ptr->pair.first)
            ptr = ptr->rightChild;
        else
            ptr = ptr->leftChild;
    }

    //ptr指向空，则未找到值为v的节点
    if (ptr == nullptr) {
        cout << "No such node in tree." << endl;
        return;
    }

    treeSize--;
    //首先进行BST删除
    if (ptr->leftChild != nullptr && ptr->rightChild != nullptr) {
        //寻找左子树最大节点
        AVLTreeNode<K, E>* leftMax = ptr->leftChild;
        AVLTreeNode<K, E>* leftMaxParent = ptr;

        while (leftMax->rightChild != nullptr) {
            s.push(leftMax);//q节点沉降至实际删除节点的父节点位置
            leftMaxParent = leftMax;
            leftMax = leftMax->rightChild;
        }
        //此时，无需关注过多细节，只需要考虑两种情况：
        //1.leftMax是其父节点的左孩子
        //2.leftMax是其父节点的右孩子
        //注意，leftMax的右孩子必为nullptr
        ptr->pair = leftMax->pair;
        if (leftMax == leftMaxParent->leftChild)
            leftMaxParent->leftChild = leftMax->leftChild;
        else if (leftMax == leftMaxParent->rightChild)
            leftMaxParent->rightChild = leftMax->leftChild;
        delete leftMax;
        (s.top())->bf--;//左孩子删除
    }
    else {
        //情况1、2
        //获取ptr可能存在的孩子指针
        AVLTreeNode<K, E>* child;
        if (ptr->leftChild != nullptr)
            child = ptr->leftChild;
        else
            child = ptr->rightChild;

        if (ptr == root)
        {
            //被删除节点为根节点，且至多有1棵子树
            root = child;
            break;
        }
        else if (ptr == pre->leftChild)
        {
            pre->leftChild = child;
            (s.top())->bf--;//左孩子删除
        }
        else if (ptr == pre->rightChild)
        {
            pre->rightChild = child;
            (s.top())->bf++;//右孩子删除
        }

        delete ptr;
    }

    /*
    * 这里注意，与插入不同，bf的计算是从底向上的
    * 也就意味着不应先计算bf再调整，但被删除节点的父节点bf需要更新
    AVLTreeNode<K, E>* cur = root;
    while (cur!=s.top()) {
        if (cur->pair < k) {
            cur->bf++;
            cur = cur->rightChild;
        }
        else {
            cur->bf--;
            cur = cur->leftChild;
        }
    }
    */

    //现在，s中保存的是root至被删除节点父节点路径上的全部节点
    //下面进行平衡调整
    bool isAllRight = false;
    while (!s.empty()||isAllRight) {
        switch (s.top()->bf) {
            case 0:{
                s.pop();
                //修改此节点的父节点bf
                if (!s.empty()) {
                    if (s.top()->bf < k)
                        s.top()->bf++;
                    else
                        s.top()->bf--;
                }
                break;
            }
            case -1:{
                isAllRight = true;
                break;
            }
            case 1: {
                isAllRight = true;
                break;
            }
            case -2: {
                //注意调整之后当前节点两侧树高可能会发生变化
                //删除只会发生在左子树
                AVLTreeNode<K, E>* right = s.top()->rightChild;
                switch (right->bf)
                {
                case 0:
                    AVLTreeNode<K, E>*rightLeft = right->leftChild;
                    AVLTreeNode<K, E>* rightRight = right->rightChild;
                    AVLTreeNode<K, E>* left = s.top()->leftChild;

                    s.top()->rightChild = rightRight;
                    s.top()->leftChild = new AVLTreeNode<K, E>(s.top()->pair);
                    s.top()->leftChild->leftChild = left;
                    s.top()->leftChild->rightChild = rightLeft;
                    s.top()->pair = right->pair;
                    delete right;
                    s.top()->bf = -1;
                    s.top()->leftChild->bf = 1;
                    s.pop();

                    //此时，以s.top()为根的树高度未变化，整棵树已平衡
                    isAllRight = true;
                    break;
                case 1:
                    AVLTreeNode<K, E>*rightLeft = right->leftChild;
                    AVLTreeNode<K, E>* rightRight = right->rightChild;
                    AVLTreeNode<K, E>* left = s.top()->leftChild;

                    s.top()->rightChild = rightRight;
                    s.top()->leftChild = new AVLTreeNode<K, E>(s.top()->pair);
                    s.top()->leftChild->leftChild = left;
                    s.top()->leftChild->rightChild = rightLeft;
                    s.top()->pair = right->pair;
                    delete right;
                    s.top()->bf = -1;
                    s.top()->leftChild->bf = 1;
                    s.pop();

                    if (!s.empty()) {
                        if (s.top()->bf < k)
                            s.top()->bf++;
                        else
                            s.top()->bf--;
                    }
                    break;
                case -1:
                    AVLTreeNode<K, E>*right = s.top()->rightChild;
                    AVLTreeNode<K, E>* left = s.top()->leftChild;
                    AVLTreeNode<K, E>* rightLeft = right->leftChild;
                    AVLTreeNode<K, E>* rightLeftRight = rightLeft->rightChild;
                    AVLTreeNode<K, E>* rightLeftLeft = rightLeft->leftChild;
                    int b = rightLeft->bf;

                    right->leftChild = rightLeftRight;
                    s.top()->leftChild = new AVLTreeNode<K, E>(s.top()->pair);
                    s.top()->lefChild->leftChild = rightLeft;
                    s.top()->leftChild->rightChild = rightLeftLeft;
                    s.top()->pair = rightLeft->pair;
                    delete rightLeft;

                    s.top()->bf = 0;
                    if (b == 0) {
                        s.top()->rightChild->bf = s.top()->leftChild->bf = 0;
                    }
                    else if (b == 1) {
                        s.top()->rightChild->bf = 0;
                        s.top()->leftChild->bf = -1;
                    }
                    else {
                        s.top()->rightChild->bf = 1;
                        s.top()->leftChild->bf = 0;
                    }
                    s.pop();

                    if (!s.empty()) {
                        if (s.top()->bf < k)
                            s.top()->bf++;
                        else
                            s.top()->bf--;
                    }
                    break;
                default:
                    cout << "Wrong bf in TreeNode in internal switch." << endl;
                    break;
                }
                break;
            }
            case 2: {
                //注意弹栈后要调整父节点的bf，因为调整之后当前节点两侧树高可能会发生变化
                //删除只会发生在右子树
                AVLTreeNode<K, E>* left = s.top()->leftChild;
                switch (left->bf)
                {
                case 0: 
                    AVLTreeNode<K, E>*leftRight = left->rightChild;
                    AVLTreeNode<K, E>* leftLeft = left->leftChild;
                    AVLTreeNode<K, E>* right = s.top()->rightChild;
                    
                    s.top()->leftChild = leftLeft;
                    s.top()->rightChild = new AVLTreeNode<K, E>(s.top()->pair);
                    s.top()->rightChild->rightChild = right;
                    s.top()->rightChild->leftChild = leftRight;
                    s.top()->pair = left->pair;
                    delete left;
                    s.top()->bf = -1;
                    s.top()->rightChild->bf = 1;
                    s.pop();

                    //此时，以s.top()为根的树高度未变化，整棵树已平衡
                    isAllRight = true;
                    break;
                case 1: 
                    AVLTreeNode<K, E>*leftRight = left->rightChild;
                    AVLTreeNode<K, E>* leftLeft = left->leftChild;
                    AVLTreeNode<K, E>* right = s.top()->rightChild;

                    s.top()->leftChild = leftLeft;
                    s.top()->rightChild = new AVLTreeNode<K, E>(s.top()->pair);
                    s.top()->rightChild->rightChild = right;
                    s.top()->rightChild->leftChild = leftRight;
                    s.top()->pair = left->pair;
                    delete left;
                    s.top()->bf = 0;
                    s.top()->rightChild->bf = 0;
                    s.pop();

                    if (!s.empty()) {
                        if (s.top()->bf < k)
                            s.top()->bf++;
                        else
                            s.top()->bf--;
                    }
                    break;
                case -1:
                    AVLTreeNode<K, E>*left = s.top()->leftChild;
                    AVLTreeNode<K, E>* right = s.top()->rightChild;
                    AVLTreeNode<K, E>* leftRight = left->rightChild;
                    AVLTreeNode<K, E>* leftRightLeft = leftRight->leftChild;
                    AVLTreeNode<K, E>* leftRightRight = leftRight->rightChild;
                    int b = leftRight->bf;

                    left->rightChild = leftRightLeft;
                    s.top()->rightChild = new AVLTreeNode<K, E>(s.top()->pair);
                    s.top()->rightChild->rightChild = leftRight;
                    s.top()->rightChild->leftChild = leftRightRight;
                    s.top()->pair = leftRight->pair;
                    delete leftRight;

                    s.top()->bf = 0;
                    if (b==0) {
                        s.top()->leftChild->bf = s.top()->rightChild->bf = 0;
                    }
                    else if (b==1) {
                        s.top()->leftChild->bf = 0;
                        s.top()->rightChild->bf = -1;
                    }
                    else {
                        s.top()->leftChild->bf = 1;
                        s.top()->rightChild->bf = 0;
                    }
                    s.pop();

                    if (!s.empty()) {
                        if (s.top()->bf < k)
                            s.top()->bf++;
                        else
                            s.top()->bf--;
                    }
                    break;
                default:
                    cout << "Wrong bf in TreeNode in internal switch." << endl;
                    break;
                }
                
                break;
            }
            default: {
                cout << "Wrong bf in TreeNode." << endl;
                return;
            }
        }
    }
}

int main() {
    AVLTree<int,int>tree;
    std::pair<int, int>* p = new std::pair<int, int>;

    delete p;
    return 0;
}